package leetcodev1.字符串;

import leetcodev1.链表.Solution;

import java.util.*;

public class LeetCode187 {

    public static void main(String[] args) {
        LeetCode187 leetCode187=new LeetCode187();
        leetCode187.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
    }

    //滑动窗口 || 双指针
    //出现不止一次
    public List<String> findRepeatedDnaSequences(String s) {
        Map<String, Integer> dict = new HashMap<>();
        int length = s.length();
        StringBuilder sb = new StringBuilder();
        //i为遍历的起点 错误
        //这里i不是起点了
        for (int i = 0; i < length; i++) {
            sb.append(s.charAt(i));

            //左边删一个
            if (sb.length() > 10) {
                sb.deleteCharAt(0);
            }

            if (sb.length() == 10) {
                dict.put(sb.toString(), dict.getOrDefault(sb.toString(), 0) + 1);
            }
        }
        List<String> ret = new ArrayList<>();
        for (Map.Entry<String, Integer> e : dict.entrySet()) {
            if (e.getValue() > 1) {
                ret.add(e.getKey());
            }
        }
        return ret;
    }

    //官方答案简洁！
    static final int L = 10;

    public List<String> findRepeatedDnaSequences1(String s) {
        List<String> ans = new ArrayList<String>();
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }

    //所有元素都是，只是看出现次数
    Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
        put('A', 0);
        put('C', 1);
        put('G', 2);
        put('T', 3);
    }};

    //位图 学到了
    public List<String> findRepeatedDnaSequences2(String s) {
        List<String> ans = new ArrayList<String>();
        //异常处理
        int n = s.length();
        if (n <= L) {
            return ans;
        }
        //每两位代表一个表示 10*2=20位
        //前10位进行存储
        int x = 0;
        for (int i = 0; i < L - 1; ++i) {
            x = (x << 2) | bin.get(s.charAt(i));
        }
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        //遍历所有起点
        for (int i = 0; i <= n - L; ++i) {
            //x <<2左移两位 将需要新加入的位置设为00
            //x = x | bin[ch]设置二进制位
            //x = x & ((1 << 20) - 1)高位全部置0 类似于滑动窗口的去旧值
            //算出最新的x 相同元素x相同
            x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);//计数
            //立即判断，只在等于2的时候add
            if (cnt.get(x) == 2) {
                ans.add(s.substring(i, i + L));//统计
            }
        }
        return ans;
    }
}
